package com.qisi.kandroidshalon.leetcode.binary.tree;

import android.util.Log;

import java.util.ArrayList;
import java.util.Comparator;
import java.util.HashMap;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.Set;
import java.util.Stack;
import java.util.TreeSet;

public class BinaryTree {
    private static final String TAG = "BinaryTree";

    /**
     * 递归前序遍历
     *
     * @param head
     */
    public static void preOrder(TreeNode head) {
        if (head == null) {
            return;
        }

        Log.i(TAG, "" + head.val);
        preOrder(head.left);
        preOrder(head.right);
    }


    /**
     * 递归中序遍历
     *
     * @param head
     */
    public static void midOrder(TreeNode head) {
        if (head == null) {
            return;
        }
        midOrder(head.left);
        Log.i(TAG, "" + head.val);
        midOrder(head.right);
    }

    /**
     * 递归中序遍历
     *
     * @param head
     */
    public static void backOrder(TreeNode head) {
        if (head == null) {
            return;
        }

        backOrder(head.left);
        backOrder(head.right);
        Log.i(TAG, "" + head.val);
    }

    /**
     * 前序遍历-迭代方式
     * 思路: 引入栈，
     * 1.头节点先入堆
     * 2.弹出打印，先进右节点，再进左节点
     * 3.重复2，直到为空栈
     */
    public static void preOrderItr(TreeNode head) {
        if (head == null) {
            return;
        }
        Stack<TreeNode> stack = new Stack<>();
        stack.push(head);
        while (!stack.isEmpty()) {
            TreeNode cur = stack.pop();
            Log.i(TAG, "非递归" + cur.val);
            if (cur.right != null) {
                stack.push(cur.right);
            }

            if (cur.left != null) {
                stack.push(cur.left);
            }
        }
    }


    /**
     * 后序遍历-迭代方式
     * 思路: 引入两个栈，一个用于收集临时的子节点，先左后右，一个用于输出节点
     * 1.头节点先入临时栈
     * 2.临时栈弹栈到输出栈，子节点先左后右入临时栈
     * 3.重复2，直到为临时栈空栈
     * 4.弹出输出栈，就能保持父节点后输出，
     */
    public static void backOrderItr(TreeNode head) {
        if (head == null) {
            return;
        }
        //临时栈
        Stack<TreeNode> stack = new Stack<>();
        //输出栈
        Stack<TreeNode> outStack = new Stack<>();
        stack.push(head);
        while (!stack.isEmpty()) {
            TreeNode cur = stack.pop();
            outStack.push(cur);
            if (cur.left != null) {
                stack.push(cur.left);
            }
            if (cur.right != null) {
                stack.push(cur.right);
            }
        }

        while (!outStack.isEmpty()) {
            TreeNode cur = outStack.pop();
            Log.i(TAG, "非递归后序遍历 " + cur.val);
        }
    }

    /**
     * 中序遍历-迭代
     * 思路：
     * 1.先遍历树的左边界，节点入栈，保证左子树先遍历
     * 2.弹出当前节点，打印，如果当前节点有右子树，则把右节点的左边界压栈，重复过程2
     *
     * @param head
     */
    public static void midOrderItr(TreeNode head) {
        if (head == null) {
            return;
        }
        //临时栈
        Stack<TreeNode> stack = new Stack<>();
        //先压一遍左边界
        TreeNode cur = head;
        while (cur != null) {
            stack.push(cur);
            cur = cur.left;
        }


        while (!stack.isEmpty()) {
            cur = stack.pop();
            Log.i(TAG, "非递归中序遍历" + cur.val);
            if (cur.right != null) {
                cur = cur.right;
                //有右节点，则右节点的左边界入站
                while (cur != null) {
                    stack.push(cur);
                    cur = cur.left;
                }
            }
        }
    }

    /**
     * 层序遍历
     * 思路: 引入队列，入队顺序 头-左-右
     *
     * @param head
     */
    public static void bfsTree(TreeNode head) {
        if (head == null) {
            return;
        }
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(head);
        while (!queue.isEmpty()) {
            TreeNode cur = queue.poll();
            Log.i(TAG, "层序遍历 " + cur.val);
            if (cur.left != null) {
                queue.offer(cur.left);
            }

            if (cur.right != null) {
                queue.offer(cur.right);
            }
        }
    }

    /**
     * 层序遍历扩展，统计各个层的节点个数
     *
     * @param head
     * @return
     */
    public static int widthOfBinaryTree(TreeNode head) {
        if (head == null) {
            return 0;
        }
        Queue<TreeNode> queue = new LinkedList<>();
        List<Integer> codes = new ArrayList<>();
        queue.offer(head);
        int level = 1;//当前弹出节点的层数
        Map<TreeNode, Integer> nodeAtLevel = new HashMap<>();//节点所在的层数
        Map<Integer, Integer> numAtLevel = new HashMap<>();//层数上的节点个数
        nodeAtLevel.put(head, 1);
        while (!queue.isEmpty()) {
            TreeNode cur = queue.poll();
            if (nodeAtLevel.get(cur) != level) {
                level++;
            }
            //弹出节点，层节点计数++
            if (numAtLevel.get(level) == null) {
                numAtLevel.put(level, 1);
            } else {
                numAtLevel.put(level, numAtLevel.get(level) + 1);
            }


            if (cur.left != null) {
                queue.offer(cur.left);
                nodeAtLevel.put(cur.left, level + 1);
            }

            if (cur.right != null) {
                queue.offer(cur.right);
                nodeAtLevel.put(cur.right, level + 1);
            }
        }

        //打印统计结果
        Set<Map.Entry<Integer, Integer>> entries = numAtLevel.entrySet();
        for (Map.Entry<Integer, Integer> entry : entries) {
            Log.i(TAG, "层：" + entry.getKey() + ", 数" + entry.getValue());
        }

        return 0;
    }


    /**
     * LeetCode 662 给你一棵二叉树的根节点 root ，返回树的 最大宽度 。
     * <p>
     * 树的 最大宽度 是所有层中最大的 宽度 。
     * <p>
     * 每一层的 宽度 被定义为该层最左和最右的非空节点（即，两个端点）之间的长度。将这个二叉树视作与满二叉树结构相同，两端点间会出现一些延伸到这一层的 null 节点，这些 null 节点也计入长度。
     * <p>
     * 题目数据保证答案将会在  32 位 带符号整数范围内。
     * 思路：利用层序遍历，给节点编号,按层弹出，计算每一层的最小和最大编号，得出差值。
     */
    public static int widthOfBinaryTree1(TreeNode head) {
        if (head == null) {
            return 0;
        }
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(head);
        Map<TreeNode, Integer> map = new HashMap<>();//节点到索引的映射
        map.put(head, 1);
        int max = Integer.MIN_VALUE;
        while (!queue.isEmpty()) {
            int start = -1;
            int end = -1;
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                TreeNode cur = queue.poll();
                int index = map.get(cur);
                if (i == 0) {
                    start = index;
                }

                if (i == size - 1) {
                    end = index;
                }

                if (cur.left != null) {
                    queue.offer(cur.left);
                    map.put(cur.left, 2 * index);
                }

                if (cur.right != null) {
                    queue.offer(cur.right);
                    map.put(cur.right, 2 * index + 1);
                }
            }
            max = Math.max(max, (end - start + 1));
        }
        Log.i(TAG, "max = " + max);
        return max;


    }

    /**
     * leetcode 958
     * 给你一棵二叉树的根节点 root ，请你判断这棵树是否是一棵 完全二叉树 。
     * <p>
     * 在一棵 完全二叉树 中，除了最后一层外，所有层都被完全填满，并且最后一层中的所有节点都尽可能靠左。
     * 最后一层（第 h 层）中可以包含 1 到 2h 个节点。
     * <p>
     * 思路: 利用层序遍历,每次遍历节点执行下面的判断
     * 1.如果节点只有右孩子，则返回false ->left == null && right != null
     * 2.条件1不满足，则如果曾经遇到过残缺的节点，且当前节点不是叶子节点,则返回
     */
    public static boolean isCompleteTree(TreeNode root) {
        if (root == null) {
            return false;
        }

        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        //遇到不是双全节点的标记,包括叶子节点
        boolean noFullNodeFlag = false;
        TreeNode left = null;
        TreeNode right = null;
        while (!queue.isEmpty()) {
            TreeNode cur = queue.poll();
            left = cur.left;
            right = cur.right;
            //只有右孩子,则返回
            if (left == null && right != null) {
                return false;
            }
            //遇到过残缺节点，且当前节点不是叶子节点，则表示本层不是完全的
            if (noFullNodeFlag && (left != null || right != null)) {
                return false;
            }

            if (left == null || right == null) {
                noFullNodeFlag = true;
            }

            if (left != null) {
                queue.offer(left);
            }

            if (right != null) {
                queue.offer(right);
            }

        }
        return true;
    }

    /**
     * 给你一个二叉树的根节点 root ，判断其是否是一个有效的二叉搜索树。
     * <p>
     * 有效 二叉搜索树定义如下：
     * <p>
     * 节点的左子树只包含 小于 当前节点的数。
     * 节点的右子树只包含 大于 当前节点的数。
     * 所有左子树和右子树自身必须也是二叉搜索树。
     * <p>
     * 思路:搜索树中序遍历,是升序，所以在
     */
    private static long preVal = Long.MIN_VALUE;

    public static boolean isValidBST(TreeNode root) {
        //走到叶子节点了，返回true
        if (root == null) {
            return true;
        }
        boolean left = isValidBST(root.left);
        //左子树不是平衡二叉树
        if (!left) {
            return false;
        }
        //中序遍历不是递增
        if (root.val <= preVal) {
            return false;
        }
        preVal = root.val;
        Log.i(TAG, "isValidBST:" + root.val);
        return isValidBST(root.right);
    }

    /**
     * LeetCode174
     * 某公司组织架构以二叉搜索树形式记录，节点值为处于该职位的员工编号。请返回第 cnt 大的员工编号。
     * 思路: 搜索树中序遍历是递增的，反过来：右-中-左是递减，在递归中统计计数和序号
     *
     * @param root
     * @param cnt
     * @return
     */
    static int n = 0;//计数
    static int result = 0;//返回结果

    public static int findTargetNode(TreeNode root, int cnt) {
        if (root == null) {
            return 0;
        }
        int right = findTargetNode(root.right, cnt);
        if (right != 0) {
            return right;
        }
        n++;
        if (n == cnt) {
            result = root.val;
            return result;
        }

        return findTargetNode(root.left, cnt);
    }


    /**
     * 104. 二叉树的最大深度
     * 给定一个二叉树 root ，返回其最大深度。
     * <p>
     * 二叉树的 最大深度 是指从根节点到最远叶子节点的最长路径上的节点数。
     * <p>
     * 思路： 拿到左右子树的最大深度，取较大值+1，往上递归
     */

    public int maxDepth(TreeNode root) {
        if (root == null) {
            return 0;
        }

        int left = maxDepth(root.left);
        int right = maxDepth(root.right);
        return Math.max(left, right) + 1;
    }

    /**
     * 111. 二叉树的最小深度
     * 给定一个二叉树，找出其最小深度。
     * <p>
     * 最小深度是从根节点到最近叶子节点的最短路径上的节点数量。
     * <p>
     * 思路:
     * 1.basecase: 节点为空 返回0;节点为叶子节点：返回1
     * 2.如果左右子树有一个为空，则返回不为空的深度
     * 3.如果左右子树均不为空，则返回二者的小值
     *
     * @param root
     * @return
     */
    public int minDepth(TreeNode root) {
        if (root == null) {
            return 0;
        }
        //到达叶子节点
        if (root.left == null && root.right == null) {
            return 1;
        }

        int l = minDepth(root.left);
        int r = minDepth(root.right);
        //有一个为空，则返回非空的深度
        if (root.left == null || root.right == null) {
            return l + r + 1;
        }

        //都不为空
        return Math.min(l, r) + 1;
    }


    /**
     * LeetCode 194. 二叉树的最近公共祖先
     * 给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。
     * <p>
     * 百度百科中最近公共祖先的定义为：“对于有根树 T 的两个结点 p、q，最近公共祖先表示为一个结点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”
     * <p>
     * 例如，给定如下二叉树:  root = [3,5,1,6,2,0,8,null,null,7,4]
     * <p>
     * 思路: 1. 先遍历树，存node-parent的hash表 2. 在找到节点p的路径 3,寻找q节点路径的时候，如果遇到p节点上的路径则返回
     */

    //节点到父节点的映射,头节点父节点为空
    private HashMap<TreeNode, TreeNode> table = new HashMap<>();
    private Set<TreeNode> path = new HashSet<>();

    /**
     * 此方法时间复杂度较高
     *
     * @param root
     * @param p
     * @param q
     * @return
     */
    public TreeNode lowestCommonAncestor1(TreeNode root, TreeNode p, TreeNode q) {
        dfs(root);
        TreeNode cur = p;
        //收集从p到头节点的路径
        while (cur != null) {
            path.add(cur);
            cur = table.get(cur);
        }

        cur = q;
        //收集从p到头节点的路径
        while (cur != null) {
            if (path.contains(cur)) {
                return cur;
            }
            cur = table.get(cur);
        }
        return root;
    }

    private void dfs(TreeNode head) {
        if (head == null) {
            return;
        }

        if (head.left != null) {
            table.put(head.left, head);
        }

        if (head.right != null) {
            table.put(head.right, head);
        }

        dfs(head.left);
        dfs(head.right);
    }


    /**
     * LeetCode 194. 二叉树的最近公共祖先
     * 给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。
     * <p>
     * 百度百科中最近公共祖先的定义为：“对于有根树 T 的两个结点 p、q，最近公共祖先表示为一个结点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”
     * <p>
     * 例如，给定如下二叉树:  root = [3,5,1,6,2,0,8,null,null,7,4]
     * <p>
     * 思路2:
     * 1,写一个函数f,判断是否包含p或者q,由于需要拿左右子树的信息，所以为后序递归
     * 2, a:如果p和q在左右子树，则返回当前节点
     * b:如果p和q在一个子树下，则返回当前的p或则q节点
     */
    private TreeNode lca = null;

    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        haseTreeNode(root, p, q);
        return lca;
    }

    private boolean haseTreeNode(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null) {
            return false;
        }

        boolean left = haseTreeNode(root.left, p, q);
        boolean right = haseTreeNode(root.right, p, q);

        //p q在不同的树下，则返回当前节点
        if (left && right) {
            lca = root;
            return true;
        }
        //p q在同一树下，则返回p或者q
        if ((left || right) && (root == p || root == q)) {
            lca = root;
            return true;
        }

        return left || right || root == p || root == q;
    }

    /**
     * LeetCode 107 给你二叉树的根节点 root ，返回其节点值 自底向上的层序遍历 。 （即按从叶子节点所在层到根节点所在的层，逐层从左向右遍历）
     * 思路: 引入队列，用作收集。然后引入栈用于输出
     */
    public List<List<Integer>> levelOrderBottom(TreeNode root) {
        List<List<Integer>> res = new LinkedList<>();
        if (root == null) {
            return res;
        }
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            int size = queue.size();
            //先遍历一层
            List<Integer> levelNodes = new LinkedList<>();
            for (int i = 0; i < size; i++) {
                TreeNode cur = queue.poll();
                levelNodes.add(cur.val);
                if (cur.left != null) {
                    queue.offer(cur.left);
                }
                if (cur.right != null) {
                    queue.offer(cur.right);
                }
            }
            res.add(0, levelNodes);
        }
        return res;
    }

    /**
     * leetcode 100 相同的树
     * 给你两棵二叉树的根节点 p 和 q ，编写一个函数来检验这两棵树是否相同。
     * 如果两个树在结构上相同，并且节点具有相同的值，则认为它们是相同的。
     *
     * @param p
     * @param q
     * @return
     */
    public boolean isSameTree(TreeNode p, TreeNode q) {
        return dfsSameTree(p, q);
    }

    private boolean dfsSameTree(TreeNode p, TreeNode q) {
        //到达叶子节点
        if (p == null && q == null) {
            return true;
        }
        //有一个为空，一个不为空，false
        if (p == null || q == null) {
            return false;
        }
        //如果都不为空先比较当前节点
        //当前节点不等，返回false
        if (p.val != q.val) {
            return false;
        }

        return dfsSameTree(p.left, q.left) && dfsSameTree(p.right, q.right);
    }

    /**
     * LeetCode 102 层序bianli
     */
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> res = new LinkedList<>();
        if (root == null) {
            return res;
        }
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            int size = queue.size();
            //先遍历一层
            List<Integer> levelNodes = new LinkedList<>();
            for (int i = 0; i < size; i++) {
                TreeNode cur = queue.poll();
                levelNodes.add(cur.val);
                if (cur.left != null) {
                    queue.offer(cur.left);
                }
                if (cur.right != null) {
                    queue.offer(cur.right);
                }
            }
            res.add(levelNodes);
        }
        return res;
    }

    /**
     * LeetCode101 给你一个二叉树的根节点 root ， 检查它是否轴对称。
     * 思路： 比较两棵树需要双指针，两棵树指针移动方向不一样，一个向左移动的时候，另外一个向右移动
     */
    public boolean isSymmetric(TreeNode root) {
        return isSymmetricDfs(root.left, root.right);
    }

    private boolean isSymmetricDfs(TreeNode left, TreeNode right) {
        //都遍历到叶子节点了，true
        if (left == null && right == null) {
            return true;
        }
        //一个非空，一个不空 false
        if (left == null || right == null) {
            return false;
        }
        return (left.val == right.val) && isSymmetricDfs(left.left, right.right) && isSymmetricDfs(left.right, right.left);
    }

    /**
     * 108. 将有序数组转换为二叉搜索树
     * 给你一个整数数组 nums ，其中元素已经按 升序 排列，请你将其转换为一棵
     * 平衡
     * 二叉搜索树。
     */
    public TreeNode sortedArrayToBST(int[] nums) {
        return dfsSortedArrayToBST(nums, 0, nums.length - 1);
    }

    private TreeNode dfsSortedArrayToBST(int[] nums, int left, int right) {
        if (left > right) {
            return null;
        }

        int mid = left + (right - left) / 2;
        TreeNode root = new TreeNode(nums[mid]);
        root.left = dfsSortedArrayToBST(nums, left, mid - 1);
        root.right = dfsSortedArrayToBST(nums, mid + 1, right);
        return root;
    }

    /**
     * LeetCode110 给定一个二叉树，判断它是否是
     * 平衡二叉树: 是指该树所有节点的左右子树的高度相差不超过 1。
     * <p>
     * 思路:自底向上递归，返回高度,如果高度非法则表示不平衡
     *
     * @param root
     * @return
     */
    public boolean isBalanced(TreeNode root) {
        return height(root) >= 0;
    }

    public int height(TreeNode root) {
        if (root == null) {
            return 0;
        }
        int leftHeight = height(root.left);
        int rightHeight = height(root.right);
        if (leftHeight == -1 || rightHeight == -1 || Math.abs(leftHeight - rightHeight) > 1) {
            return -1;
        } else {
            return Math.max(leftHeight, rightHeight) + 1;
        }
    }

    /**
     * LeetCode530 给你一个二叉搜索树的根节点 root ，返回 树中任意两不同节点值之间的最小差值 。
     * <p>
     * 差值是一个正数，其数值等于两值之差的绝对值。
     * 思路 中序遍历
     */
    int pre = -1;
    int ans = Integer.MAX_VALUE;

    public int getMinimumDifference(TreeNode root) {
        dfsMinMax(root);
        return ans;
    }


    /**
     * 确定一颗树的最大值最小值
     *
     * @param head
     * @return
     */
    private void dfsMinMax(TreeNode head) {
        if (head == null) {
            return;
        }
        dfsMinMax(head.left);
        if (pre == -1) {
            pre = head.val;
        } else {
            ans = Math.min(Math.abs(pre - head.val), ans);
            if (ans == 1) {
                return;
            }
            pre = head.val;
        }
        dfsMinMax(head.right);
    }

    /**
     * todo 646 贪心算法
     */

    /**
     * leetcode 295
     * 中位数是有序整数列表中的中间值。如果列表的大小是偶数，则没有中间值，中位数是两个中间值的平均值。
     * 思路: 利用大小根堆，区分大小半区，二者个数差不超过1
     */
    //小根堆
    private PriorityQueue<Integer> minHeap = new PriorityQueue<>();

    public class MaxComparator implements Comparator<Integer> {
        @Override
        public int compare(Integer a, Integer b) {
            return b - a;
        }
    }
    //大根堆
    private PriorityQueue<Integer> maxHeap = new PriorityQueue<>(new MaxComparator());

    public void addNum(int num) {
        if (maxHeap.isEmpty()) {
            maxHeap.add(num);
            return;
        }

        Integer peek = maxHeap.peek();
        if (num <= peek) {
            maxHeap.add(num);
        } else {
            minHeap.add(num);
        }

        if (maxHeap.size() - minHeap.size() > 1) {
            minHeap.add(maxHeap.poll());
        } else if(minHeap.size() - maxHeap.size() > 1) {
            maxHeap.add(minHeap.poll());
        }
    }

    public double findMedian() {
        if (maxHeap.size() > minHeap.size()) {
            return maxHeap.peek();
        } else if (maxHeap.size() < minHeap.size()) {
            return minHeap.peek();
        }
        return (maxHeap.peek() + minHeap.peek()) / 2.0;
    }

}
